package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DaiBi;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;
import java.util.List;

/**
 * 118 119
 * https://leetcode.com/problems/pascals-triangle-ii/discuss/38513/My-clean-O(k)-java-solution
 * <p>
 * Could you optimize your algorithm to use only O(k) extra space?
 * <p>
 * 用On算出来, n^2和上题啥区别啊, 没几把劲
 * <p>
 * On就得上公式了 玛德
 *
 * @author tzp
 * @since 2020/11/18
 */
public class LC119 implements DaiBi {

    public List<Integer> getRow(int rowIndex) {
        Integer[] rowList = new Integer[rowIndex + 1];
        rowList[0] = 1;
        for (int i = 1; i < rowList.length; i++) {
            rowList[i] = (int) ((long) rowList[i - 1] * (rowIndex - (i - 1)) / (i));
        }
        return Arrays.asList(rowList);
    }

    public static void main(String[] args) {
        System.out.println(new LC119());
    }
}
